package Topological;

import java.util.*;

/**
 * Created with Intellij IDEA.
 * Description;
 * User:TQ02
 * Data:2024-03-14
 * Time:20:15
 * Text：LCR 114. 火星词典
 */
public class Text3 {
    public String alienOrder(String[] words) {
        Set<List<Character>> set=new HashSet<>();
        int[] array=new int[26];
        int n=words.length;
        for(int i=0;i<26;i++){
            array[i]=-1;
        }
        for(int i=0;i<n;i++){
            String str=words[i];
            for(int j=0;j<str.length();j++){
                int k=str.charAt(j)-97;
                array[k]=-2;
            }
        }

        if(n==2 && words[0].equals(words[1])){
            return words[0];
        }
        for(int i=0;i<n;i++){
            String str=words[i];
            for(int j=i+1;j<n;j++){
                List<Character> t1=new LinkedList<>();
                String str2=words[j];
                int left=0;
                int cv=0;
                while(left<Math.min(str.length(),str2.length())){
                    if(str.charAt(left)!=str2.charAt(left)){
                        t1.add(str.charAt(left));
                        t1.add(str2.charAt(left));
                        set.add(t1);
                        cv=1;
                        break;
                    }
                    left++;
                }
                if(left<str.length() && cv!=1)
                    return new String();
            }
        }
        HashMap<Character,List<Character>> map=new HashMap<>();

        for(List<Character> t1:set){
            char l=t1.get(0),r=t1.get(1);
            int k=r-97;
            int k1=l-97;
            array[k]=0;
            array[k1]=0;
        }
        for(List<Character> t1:set){
            char l=t1.get(0),r=t1.get(1);
            int k=r-97;
            if(!map.containsKey(l)){
                map.put(l,new LinkedList<>());
            }
            map.get(l).add(r);
            array[k]++;
        }
        Queue<Character> q=new LinkedList<>();
        for(int i=0;i<26;i++){
            if(array[i]==0) {
                char c= (char)(i+'a');
                q.add(c);
            }
        }
        StringBuffer str3=new StringBuffer();
        while(!q.isEmpty()){
            char ks=q.poll();
            str3.append(ks);
            for(char a:map.getOrDefault(ks,new LinkedList<>())){
                int num=a-97;
                array[num]--;
                if(array[num]==0){
                    char num2=(char)(num+'a');
                    q.add(num2);
                }
            }
        }

        for(int i=0;i<26;i++){
            if(array[i]==-2){
                char num2=(char)(i+'a');
                str3.append(num2);
            }
            if(array[i]>0){
                return new String();
            }
        }
        return str3.toString();
    }

    public static void main(String[] args) {
        Text3 t1=new Text3();
        String[] array={"z","x","a","zb","zx"};
        t1.alienOrder(array);
    }
}
